/*
 *https://leetcode.cn/problems/longest-univalue-path/
 *687. 最长同值路径
 *medium 吴朝泽 2024.11.6
 *DFS深度优先搜索
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLength = 0; 

    int dfs(TreeNode* node) {
        if (!node) return 0;  
            
        int leftLength = dfs(node->left);  // 左子树的最长路径
        int rightLength = dfs(node->right);  // 右子树的最长路径
            
        // 当前节点的左右子树与当前节点的值相同，才能延续路径
        int leftPath = 0, rightPath = 0;
        if (node->left && node->left->val == node->val) {
            leftPath = leftLength + 1;
        }
        if (node->right && node->right->val == node->val) {
            rightPath = rightLength + 1;
        }
            
        maxLength = max(maxLength, leftPath + rightPath);
            
        // 返回当前节点的最长单值路径（只考虑单侧延续）
        return max(leftPath, rightPath);
    }

    int longestUnivaluePath(TreeNode* root) {    
        if(root == NULL)  return 0;
        dfs(root);  
        return maxLength;  
    }
};
